/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
 var minDistance = function(word1, word2) {
  // dp[i][j]表示以i-1位结尾的字符串和以j-1位结尾的字符串,想达到相等,需要删除的元素的最小次数
  let dp = new Array(word1.length+1).fill(0).map(()=>new Array(word2.length+1).fill(0))
  // 初始化 dp[i][0] 表示以i-1位结尾的字符串和空字符串相等 需要删除的元素个数 那就是 2-1位结尾的有2个 那就是要删除i个
  // dp[i][0]就是i dp[0][j]表示空字符串和一个以j-1位结尾的 同样还是j dp[0][j] = j
  for(let i = 0;i <= word1.length;i++){ // 这里是等号表示可以从0到word.length都可以
    dp[i][0] = i
  }
  for(let j = 0;j <= word2.length;j++){
    dp[0][j] = j
  }
  // 开始遍历 
  for(let i = 1;i <= word1.length;i++){
    for(let j = 1;j <= word2.length;j++){
      if(word1[i-1] == word2[j-1]){
        // 如果这个的第i-1位和第j-1位的元素相同 那么那么需要删除的操作步数就是 以i-2位结尾的和j-2为结尾的操作步数不变
        dp[i][j] = dp[i-1][j-1]
      }else{
        // 如果不相同 那么就是以i-2位结尾的和以j-2位结尾的操作多两步 和以 i-2位结尾的和以j-1位结尾的多1步 和以i-1位结尾的和以j-2位结尾的多1步
        dp[i][j] = Math.min(dp[i-1][j-1]+2,dp[i][j-1]+1,dp[i-1][j]+1)
      }
    }
  }
  return dp[word1.length][word2.length] // 最后返回以1的最后一位和2的最后一位为结尾的操作步数
};


/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
 var minDistance = function(word1, word2) {
    // dp[i][j] 表示以i-1为结尾的字符串和以j-1位结尾的字符串的最长子序列是多长
    let dp = new Array(word1.length+1).fill(0).map(()=>new Array(word2.length+1).fill(0))
    // 初始化 两个空字符串 就是0 没有最长子序列的长度 一个为空 也是0 就是没有子序列的长度
    // 递推公式 dp[i][j] 如果word1[i-1]=== word2[j-1] 那么以i-1位结尾的字符串和以j-1为结尾的字符串的最长子序列长度 就是以i-2位结尾的和以j-2位结尾的最长子序列长度 + 1
    // 如果不相等 那就是以i-1位结尾的和以j-2位结尾的最长子序列长度 和以i-2位结尾的和以j-1位结尾的最长子序列长度 两个里面的最大值
    for(let i = 1;i <= word1.length;i++){
      for(let j = 1;j <= word2.length;j++){
        if(word1[i-1] === word2[j-1]){
          dp[i][j] = dp[i-1][j-1]+1
        }else{
          dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])
        }
      }
    }
    return word1.length + word2.length - 2*dp[word1.length][word2.length] // 最后返回这个凉长度的和 - 两个的最长子序列的长度
};